// https://leetcode.cn/problems/word-break/
// Created by ade on 2022/7/27.
//
#include <iostream>
#include <string>
#include <cstring>
#include <unordered_set>
#include <vector>

using namespace std;

class Solution {
public:
    // dfs或者回溯会超时
    bool flag = false;

    bool wordBreak1(string s, vector <string> &wordDict) {
        dfs(s, wordDict);
        return flag;
    }

    void dfs(string s, vector <string> &wordDict) {
        if (s == "") {
            flag = true;
            return;
        }
        for (auto word : wordDict) {
            int len = word.size();
            if (s.substr(0, len) != word) continue;
            dfs(s.substr(len), wordDict);
        }
    }

    // 死亡翻滚法
    bool wordBreak(string s, vector <string> &wordDict) {
        int len = s.size();
        unordered_set<int> myS = {};
        for (auto word : wordDict) {
            int wordLen = word.size();
            if (s.substr(0, wordLen) != word) continue;
            myS.insert(word.size());
            if (word == s) return true;
        }

        while (1) {
            unordered_set<int> tmpS = {};
            int minIndex = 100000;
            for (auto i : myS) {
                for (auto word : wordDict) {
                    int wordLen = word.size();
                    if (s.substr(i, wordLen) != word) continue;
                    if (i + wordLen == len) return true;
                    minIndex = min(minIndex, i + wordLen);
                    tmpS.insert(i + wordLen);
                }
            }
            if (tmpS.empty())
                return false;
            myS.swap(tmpS);
            if (minIndex > len)
                break;
        }
        return false;
    }
};

int main() {
    Solution so;
    string s = "catsandog";
    vector <string> wordDict = {"cats", "dog", "sand", "and", "cat"};
    if (so.wordBreak(s, wordDict)) {
        cout << "yes" << endl;
    } else {
        cout << "no" << endl;
    }
    return 0;
}